def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


'''
定义法，效率太低
'''


def phi(n):
    tot = 0
    for i in range(1, n + 1):
        if gcd(i, n) == 1:
            tot += 1
    return tot


'''
欧拉函数计算方法
phi(1)=1
phi(p)=p-1
phi(p*q)=phi(p)*phi(q)  if gcd(p,q)=1
phi(p^k)=p^k-p^(k-1)

'''
maxn = 100
dp = [0] * maxn


def euler():  # bug
    dp[1] = 1
    for i in range(2, maxn): dp[i] = i
    for i in range(2, maxn):
        if dp[i] == i:
            for j in range(i, maxn, i):
                dp[j] = dp[j] // i * (i - 1)


print(phi(12))
euler()
print(dp)
